import java.io.*;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

class Read{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}


public class Main {
    public static Read in = new Read();
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));


    /**
     * 01背包模板
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        int maxTime = in.nextInt(), N = in.nextInt();
        int[] cost = new int[N];
        int[] value = new int[N];
        for (int i = 0; i < N; i++) {
            cost[i] = in.nextInt();
            value[i] = in.nextInt();
        }
        int[] dp = new int[maxTime + 1];
        for (int i = 0; i < N; i++) {
            for (int j = maxTime; j >= cost[i]; j--) {
                dp[j] = Math.max(dp[j] , dp[j - cost[i]] + value[i]);
            }
        }
        out.println(dp[maxTime]);
        out.close();
    }


    /**
     * 最后一个石头大小
     * @param args
     * @throws IOException
     */
    public static void main2(String[] args) throws IOException {
        int N = in.nextInt();
        int[] nums = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }
        int near = nearByNums(nums, sum/2);
        out.println(sum - near - near);
        out.close();
    }

    private static int nearByNums(int[] nums, int t) {
        int[] dp = new int[t+1];
        for (int num : nums) {
            for (int i = t; i >= num; i--) {
                dp[i] = Math.max(dp[i], dp[i - num] + num);
            }
        }
        return dp[t];
    }

    /**
     * 有依赖的背包模板
     * @param args
     */

    public static int MAXN = 33001;

    public static int MAXM = 61;

    public static int[] cost = new int[MAXM];

    public static int[] val = new int[MAXM];

    public static boolean[] king = new boolean[MAXM];

    public static int[] fans = new int[MAXM];

    public static int[][] follows = new int[MAXM][2];

    public static int[] dp = new int[MAXN];

    public static int n,m;

    public static void main3(String[] args) throws IOException {
        n = in.nextInt(); m = in.nextInt();
        for (int i = 1; i <= m; i++) {
            cost[i] = in.nextInt();
            int p = in.nextInt();
            val[i] = cost[i] * p;
            int q = in.nextInt();
            king[i] = q == 0;
            if (q != 0) {
                follows[q][fans[q]++] = i;
            }
        }
        out.println(compute2());
        out.close();
    }

    private static int compute2() {
        int[][] dp = new int[m+1][n+1];
        int p = 0;
        for (int i = 1, fan1, fan2; i <= m; i++) {
            if(king[i]) {
                for (int j = 0;j <= n; j++) {
                    dp[i][j] = dp[p][j];
                    if (j - cost[i] >= 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i]] + val[i]);
                    }
                    fan1 = fans[i] >= 1 ? follows[i][0] : -1;
                    fan2 = fans[i] >= 2 ? follows[i][1] : -1;
                    if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
                        // 可能性3 : 主 + 附1
                        dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
                    }
                    if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
                        // 可能性4 : 主 + 附2
                        dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
                    }
                    if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {
                        // 可能性5 : 主 + 附1 + 附2
                        dp[i][j] = Math.max(dp[i][j],
                                dp[p][j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
                    }
                }
                p = i;
                }
            }
         return dp[p][n];
        }

    static int mod = 1000000007;
    public static void main4(String[] args) throws IOException {
        int t = in.nextInt();
        while (t-- > 0) {
            int N = in.nextInt();
            int[] nums = new int[N];
            int sum = 0;
            int evenNumber = 0, oddNumber = 0;
            for (int i = 0; i < N; i++) {
                nums[i] = in.nextInt();
                if (((nums[i] & 1) ^ 1) == 0) {
                    oddNumber++;
                }else {
                    evenNumber++;
                }
                sum += nums[i];
            }
            if (((sum & 1) ^ 1) == 0) {
                out.println(0);
                continue;
            }
            if (evenNumber == nums.length) {
                out.println((int) Math.pow(2.0, evenNumber) % mod);
            }else {
                out.println((int) Math.pow(2.0, evenNumber + oddNumber -1) % mod);
            }
        }
        out.close();
    }

    public static void main5(String[] args) throws IOException {
        int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
        int x3 = in.nextInt(), y3 = in.nextInt(), x4 = in.nextInt(), y4 = in.nextInt();
        if (x3 >= x1&& x3 <= x2&& y3 >= y1&& y3 <= y2) {
            int M = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3) - (x2 - x3) * (y2 - y3);
            out.println(M);
        }else {
            int M = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3);
            out.println(M);
        }
        out.close();
    }

    public static void main6(String[] args) throws IOException {
        int n = in.nextInt();
        long[] nums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            nums[i] = in.nextLong();
        }
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        for (int i = 1; i < n; i++) {
            a[i] = in.nextInt();
            b[i+1] = in.nextInt();
        }
        double[][] dp = new double[n+1][2];
        dp[1][0] = nums[1];
        dp[1][1] = nums[1] + a[1]/0.7;
        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.min(dp[i-1][0] + nums[i] - nums[i-1], dp[i-1][1] + b[i]/1.3);
            if (a[i] > b[i]) {
                dp[i][1] = Math.min(dp[i-1][0] + nums[i] - nums[i-1] + a[i]/0.7,
                        dp[i-1][1] + (a[i]-b[i])/0.7);
            }else {
                dp[i][1] = Math.min(dp[i-1][0] + nums[i] - nums[i-1] + a[i]/0.7,
                        dp[i-1][1] + (b[i]-a[i])/1.3);
            }
        }
        out.printf("%.2f",dp[n][0]);
        out.close();
    }

    /**
     * 分组背包模板
     */
    static int MAX = 10001;
    static int[][] arr = new int[MAX][3];
    public static void main7(String[] args) throws IOException {
        m = in.nextInt();n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
            arr[i][2] = in.nextInt();
        }
        Arrays.sort(arr, 1, n+1, (a, b) -> a[2] - b[2]);
        int[] dp = new int[m+1];
        for (int start = 1, end = 2; start <= n;) {
            while (end <= n&& arr[start][2] == arr[end][2]) {
                end++;
            }
            for (int i = m; i >= 0; i--) {
                for (int j = start; j < end; j++) {
                    if(i - arr[j][0] >= 0) {
                        dp[i] = Math.max(dp[i], dp[i - arr[j][0]] + arr[j][1]);
                    }
                }
            }
            start = end++;
        }
        out.println(dp[m]);
        out.close();
    }

    public int maxValueOfCoins(List<List<Integer>> piles, int m) {
        int[] dp = new int[m+1];
        for (List<Integer> team:piles) {
            int t = Math.min(team.size(),m);
            int[] preSum = new int[t+1];
            for (int j = 0, sum = 0; j < t; j++) {
                sum += team.get(j);
                preSum[j+1] = sum;
            }
            for (int j = m; j >= 0; j--) {
                for (int k = 1; k <= Math.min(t,j); k++) {
                    dp[j] = Math.max(dp[j], dp[j-k] + preSum[k]);
                }
            }
        }
        return dp[m];
    }

    /**
     * 完全背包模板
     * @param args
     * @throws IOException
     */
    public static void main15(String[] args) throws IOException {
        int t = in.nextInt(), m = in.nextInt();
        int[] cost = new int[m+1];
        int[] val = new int[m+1];
        for (int i = 1; i <= m; i++) {
            cost[i] = in.nextInt();
            val[i] = in.nextInt();
        }
        int[] dp = new int[t+1];
        for (int i = 1; i <= m; i++) {
            for (int j = cost[i]; j <= t; j++) {
                dp[j] = Math.max(dp[j], dp[j-cost[i]]+val[i]);
            }
        }
        out.println(dp[t]);
        out.close();
    }

    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob(nums,2,n-2),rob(nums,1,n-1));
    }
    public int rob(int[] nums, int start, int end) {
        if(start > end) {
            return 0;
        }
        int[] f = new int[nums.length], g = new int[nums.length];
        f[start] = nums[start];
        for(int i = start + 1;i <= end;i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[end], g[end]);
    }


    /**
     * 正则表达式匹配
     * @param str
     * @param pat
     * @return
     */
    public boolean isMatch1(String str, String pat) {
        char[] s = str.toCharArray();
        char[] p = pat.toCharArray();
        return f1(s, p, 0, 0);
    }
    public boolean f1(char[] s, char[] p, int i, int j) {
        if(i == s.length) {
            if(j == p.length) return true;
            else return j+1 < p.length&&p[j+1] == '*'&&f1(s, p, i, j+2);
        }else if(j == p.length){
            return false;
        }else {
            if(j+1 == p.length||p[j+1] != '*') {
                return (s[i] == p[j]||p[j] == '.')&&f1(s, p, i+1, j+1);
            }
            else {
                boolean b1 = f1(s, p, i, j+2);
                boolean b2 = (s[i] == p[j]||p[j] == '.')&& f1(s, p, i + 1, j);
                return b1||b2;
            }
        }
    }

    public boolean isMatch2(String str, String pat) {
        char[] s = str.toCharArray();
        char[] p = pat.toCharArray();
        int n = s.length, m = p.length;
        int[][] dp = new int[n+1][m+1];
        // dp[i][j] == 0没算过 == 1 结果为true ==2结果为false
        return f2(s, p, 0, 0, dp);
    }

    private boolean f2(char[] s, char[] p, int i, int j, int[][] dp) {
        if(dp[i][j] > 0) {
            return dp[i][j] == 1;
        }
        boolean ans;
        if (i == s.length) {
            if (j == p.length) {
                ans = true;
            }else {
                ans = j+1 < p.length && p[j+1] == '*' &&f2(s, p, i, j+2, dp);
            }
        } else if (j == p.length) {
            ans = false;
        }else {
            if (j+1 == p.length||p[j+1] != '*') {
                ans = (p[j] == s[i]||p[j] == '.')&&f2(s, p, i+1, j+1, dp);
            }
            else {
                boolean b1 = f2(s, p, i, j+2, dp);
                boolean b2 = (p[j] == s[i]||p[j] == '.')&&f2(s, p, i+1, j, dp);
                ans = b1||b2;
            }
        }
        dp[i][j] = ans?1:2;
        return ans;
    }

    public boolean isMatch3(String str, String pat) {
        char[] s = str.toCharArray();
        char[] p = pat.toCharArray();
        int n = s.length, m = p.length;
        boolean[][] dp = new boolean[n+1][m+1];
        dp[n][m] = true;
        for (int i = m-1; i >= 0; i--) {
            dp[n][i] = i+1 < m&&p[i+1] == '*'&&dp[n][i+2];
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = m-1; j >= 0; j--) {
                if(j+1 == m||p[j+1] != '*') {
                    dp[i][j] = (p[j] == s[i]||p[j] == '.')&&dp[i+1][j+1];
                }else {
                    dp[i][j] = dp[i][j+2] || (p[j] == s[i]||p[j] == '.')&&dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len+1][m+1][n+1];
        for(int i = 1; i <= len; i++) {
            int a = 0,b = 0;
            for(char ch:strs[i-1].toCharArray()) {
                if(ch == '0') a++;
                else b++;
            }
            for(int j = 0;j <= m;j++) {
                for(int k = 0;k <= n;k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= a&&k >= b) {
                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-a][k-b]+1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    public int getMoneyAmount(int n) {
        int[][] mem = new int[n+1][n+1];
        return dfs(1,n,mem);
    }
    public int dfs(int left, int right, int[][] mem) {
        if(left >= right) {
            return 0;
        }
        if(mem[left][right] != 0){
            return mem[left][right];
        }
        int ret = Integer.MAX_VALUE;
        for(int i = left;i < right;i++) {
            int m = dfs(left,i - 1,mem);
            int n = dfs(i+1,right,mem);
            ret = Math.min(Math.max(m,n) + i,ret);
        }
        mem[left][right] = ret;
        return ret;
    }

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[n+1][minProfit+1];
        int MOD = (int)1e9 + 7;
        int len = group.length;
        for (int j = 0;j <= n;j++) dp[j][0] = 1;
        for(int i = 0;i < len;i++) {
            for (int j = n;j >= group[i];j--) {
                for(int k = 0;k <= minProfit;k++) {
                    dp[j][k] +=  dp[j - group[i]][Math.max(0,k - profit[i])];
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[n][minProfit];
    }

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0;i < coins.length;i++) {
            for (int j = coins[i];j <= amount;j++) {
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}